UVa/11513 - 9-Puzzle/puzzle.cpp

   1 /*
   2   Problem: H - 9-Puzzle
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6  */
   7
   8 using namespace std;
   9 #include <algorithm>
  10 #include <iostream>
  11 #include <iterator>
  12 #include <sstream>
  13 #include <fstream>
  14 #include <cassert>
  15 #include <climits>
  16 #include <cstdlib>
  17 #include <cstring>
  18 #include <string>
  19 #include <cstdio>
  20 #include <vector>
  21 #include <cmath>
  22 #include <queue>
  23 #include <deque>
  24 #include <stack>
  25 #include <map>
  26 #include <set>
  27
  28 #define _for(i, a, b) for (int i=0, _n = b; i<_n; ++i)
  29 #define _from(i, a, b) for (int i=a, _n = b; i>=_n; --i)
  30
  31 #define D(x) cout << #x " is " << x << endl
  32
  33 struct state { int s[3][3]; };
  34
  35 int encode(const state &s){ int r = 0; _for(i, 0, 3) _for(j, 0, 3) r = 10*r + s.s[i][j]; return r; }
  36 void decode(int r, state &s) { _from(i, 2, 0) _from(j, 2, 0) s.s[i][j] = r%10, r/=10; }
  37
  38
  39 map<int, int> prev;
  40 map<int, string> choice;
  41
  42 void bfs(){
  43   queue<int> q;
  44   prev[123456789] = -1;
  45   q.push(123456789);
  46   while (q.size()){
  47     int x = q.front();
  48     q.pop();
  49     //D(x);
  50
  51     state u; decode(x, u);
  52     //Horizontal
  53     for(int i=0, t; i<3; ++i){
  54       state v = u;
  55       t = v.s[i][0], v.s[i][0] = v.s[i][1], v.s[i][1] = v.s[i][2], v.s[i][2] = t;
  56       int y = encode(v);
  57       if (!prev.count(y)) prev[y] = x, choice[y] = string("H") + char(i+'1'), q.push(y);
  58     }
  59
  60     //Vertical
  61     for(int i=0, t; i<3; ++i){
  62       state v = u;
  63       t = v.s[2][i], v.s[2][i] = v.s[1][i], v.s[1][i] = v.s[0][i], v.s[0][i] = t;
  64       int y = encode(v);
  65       if (!prev.count(y)) prev[y] = x, choice[y] = string("V") + char(i+'1'), q.push(y);
  66     }
  67   }
  68 }
  69
  70 int main(){
  71   //assert(freopen("puzzle.in", "r", stdin) != NULL);
  72   bfs();
  73   for (int u, x; !(u = 0);){
  74     for (int i=0; i<9; ++i) cin >> x, u = 10*u + x;
  75     if (u == 0) break;
  76     if (!prev.count(u)) cout << "Not solvable" << endl;
  77     else{
  78       string s = "";
  79       for (int w = prev[u]; w != -1; w = prev[u = w]) s += choice[u];
  80       cout << s.size() / 2 << " " << s << endl;
  81     }
  82   }
  83   return 0;
  84 }